package com.javabasic.algorithm.leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/7/9 22:52
 * @Version 1.0
 **/
public class ReSpaceLCCI {


    public int respace(String[] dictionary, String sentence) {
        Arrays.sort(dictionary,new Comparator<String>() {

            @Override
            public int compare(String s1, String s2) {
                if (s1.contains(s2)) {
                    return -1;
                } else if (s1.length() > s2.length()){
                    return 1;
                } else {
                    return 0;
                }
            }
        });
        int len = dictionary.length;
        for (int i = 0; i < len; i++) {
            System.out.print(dictionary[i] + " ");
            sentence = sentence.replaceAll(dictionary[i]," ");
        }
        System.out.println();
        int length = sentence.length();
        int result = 0;
        System.out.println(sentence);
        for (int i = 0; i < length; i++) {
            if (sentence.charAt(i) >= 'a' && sentence.charAt(i) <= 'z') {
                result++;
            }
        }
        return result;

    }


    public int respace2(String[] dictionary, String sentence) {

        int len = dictionary.length;

        return dfs(sentence,dictionary,len-1);

    }

    private int dfs(String sentence,String[] dictionary, int k) {
        if (k == -1) {
            return sentence.length();
        }
        if (sentence.contains(dictionary[k])) {
//            dfs(sentence.replace(dictionary[k],""),dictionary,k);
//            dfs(sentence.replace(dictionary[k],""),dictionary,k-1);
//            dfs(sentence,dictionary,k-1);
            return Math.min(dfs(sentence.replaceFirst(dictionary[k],""),dictionary,k),dfs(sentence,dictionary,k-1));
        } else {
            return dfs(sentence,dictionary,k-1);
        }

    }


    private int dfs2(String sentence,String[] dictionary, int k) {
        if (k == -1) {
            return sentence.length();
        }
        int result = Integer.MAX_VALUE, temp;
        for (int i = 0; i < k; i++) {
            if (sentence.contains(dictionary[k])) {
                temp = Math.min(dfs(sentence.replaceFirst(dictionary[k],""),dictionary,k),
                        dfs(sentence,dictionary,k));
            } else {
                temp = dfs(sentence,dictionary,k);
            }
            if (temp < result) {
                result = temp;
            }
        }
        return result;

    }

    // 获取字符串的有效长度
    public int getValidateLen(String str) {
        int length = str.length();
        int result = 0;
        for (int i = 0; i < length; i++) {
            if (str.charAt(i) >= 'a' && str.charAt(i) <= 'z') {
                result++;
            }
        }
        return result;
    }


    /**
     * 动态规划解法：
     * dp[i] 表示 0-i的最小不能被识别的字母个数
     * 求 dp[k] 如果第K个字母 不能和前面的字母[0-{k-1}]合在一起被识别  那么dp[k] = dp[k-1]+1
     * 如果可以别识别 dp[k] = min(dp[k],dp[j-1])
     *
     * 能不能被识别的判断又有几种解法：
     * 1. 使用HashMap  -- 本题解使用HashMap
     * 2. 使用字典树
     * 3. RK算法
     * 参考链接：https://leetcode-cn.com/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/
     * @param dictionary
     * @param sentence
     * @return
     */
    public int respace3(String[] dictionary, String sentence) {


        HashMap<String, Integer> map = new HashMap<>();
        for (String s : dictionary) {
            map.put(s,1);
        }
        int length = sentence.length();
        int[] dp = new int[length+1];
        // 由于边界的处理我们让dp[i+1] 表示0-i的最小不能被识别的字母个数
        for (int i = 0; i < length; i++) {
            dp[i+1] = dp[i]+1;
            for (int j = 0; j <= i; j++) {
                if (map.getOrDefault(sentence.substring(j,i+1),0) == 1) {
                    dp[i+1] = Math.min(dp[i+1],dp[j]);
                }
            }
        }
        return dp[length];

    }

}
